By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 36, Issue 2, pp. 281-561

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up

Fedor V. Fomin and Dimitrios M. Thilikos

pp. 281-309

BibTeX  Abstract Full Text:  PDF

Between O(nm) and O(nalpha)

Dieter Kratsch and Jeremy Spinrad

pp. 310-325

BibTeX  Abstract Full Text:  PDF

Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs

Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, and Jeremy P. Spinrad

pp. 326-353

BibTeX  Abstract Full Text:  PDF

Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing

Yair Bartal, Amos Fiat, and Stefano Leonardi

pp. 354-393

BibTeX  Abstract Full Text:  PDF

Efficient Bundle Sorting

Yossi Matias, Eran Segal, and Jeffrey Scott Vitter

pp. 394-410

BibTeX  Abstract Full Text:  PDF

Approximation Algorithms for Metric Facility Location Problems

Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang

pp. 411-432

BibTeX  Abstract Full Text:  PDF

An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem

Michael Elkin

pp. 433-456

BibTeX  Abstract Full Text:  PDF

Toward a Topological Characterization of Asynchronous Complexity

Gunnar Hoest and Nir Shavit

pp. 457-497

BibTeX  Abstract Full Text:  PDF

Covering Problems with Hard Capacities

Julia Chuzhoy and Joseph (Seffi) Naor

pp. 498-515

BibTeX  Abstract Full Text:  PDF

Properties of NP-Complete Sets

Christian Glaßer, A. Pavan, Alan L. Selman, and Samik Sengupta

pp. 516-542

BibTeX  Abstract Full Text:  PDF

The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals

Jon Feldman and Matthias Ruhl

pp. 543-561

BibTeX  Abstract Full Text:  PDF